// -排序练习2-  交换排序 20221223
#include <iostream>
#include <vector>
using namespace std;

namespace MySort
{
    // 冒泡排序
    template<class T>
    void BubbleSort(vector<T>& v)
    {
        int n = v.size();

        for (int i = 0; i < n; ++i)
        {
            int flag = 1;
            for (int j = 0; j < n - i - 1; j++)
            {
                if (v[j + 1] < v[j])
                {
                    flag = 0;
                    swap(v[j + 1], v[j]);
                } 
            }
            if (flag) break;
        }
    }

    // 声明
    template<class T> void _QuickSort(vector<T>& v, int left, int right);  // 递归子函数
    template<class T> int _quickSort1(vector<T>& v, int left, int right);  // 算法1

    // 快速排序
    template<class T>
    void QuickSort(vector<T>& v)
    {
        // 分治算法
        _QuickSort(v, 0, v.size() - 1);
    }

    template<class T>
    void _QuickSort(vector<T>& v, int left, int right)
    {
        if (left >= right) return;

        int middle = _quickSort1(v, left, right);
        // 递归进行处理
        _QuickSort(v, left, middle - 1);
        _QuickSort(v, middle + 1, right);
    }

    // 优化1 -三数取中法-
    template<class T>
    void ThreeNumberMiddle(vector<T>& v, int left, int right)
    {
        int m = left + (right - left) / 2;
        if (v[left] > v[m])
        {
            if (v[m] > v[right]) swap(v[m], v[left]);
            else if (v[left] > v[right]) swap(v[right], v[left]);
        }
        else
        {
            if (v[right] > v[m]) swap(v[m], v[left]);
            else if (v[right] > v[left]) swap(v[right], v[left]);
        }
    }

    // 算法1 -原始版本-
    template<class T>
    int _quickSort1(vector<T>& v, int left, int right)
    {
        // 首先先进行一个三数取中法
        ThreeNumberMiddle(v, left, right);
        int target = left++;

        while (left < right)
        {
            // 右边先走 右找小
            while (left < right && v[right] >= v[target])
            {
                right--;
            }

            while (left < right && v[left] <= v[target])
            {
                left++;
            }

            swap(v[left], v[right]);
        }
        if (v[left] < v[target])
        {
            swap(v[left], v[target]);
            target = left;
        }
        return target;
    }
}

int main()
{
    vector<int> arr1 = {1, 2, 7, 0, -1, 4, 8};
    vector<int> arr2 = {1, 2, 3, 4, 5, 6, 7};
    vector<int> arr3 = {7, 6, 5, 4, 3, 2, 1};

    // 1冒泡排序
    // MySort::BubbleSort(arr1);
    // MySort::BubbleSort(arr2);
    // MySort::BubbleSort(arr3);

    // 2快速排序
    MySort::QuickSort(arr1);
    MySort::QuickSort(arr2);
    MySort::QuickSort(arr3);


    for (auto e : arr1)
    {
        cout << e << " ";
    }
    cout << endl;
    for (auto e : arr2)
    {
        cout << e << " ";
    }
    cout << endl;
    for (auto e : arr3)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}